\documentclass[%
    a4paper,
    10pt,
    final,
    notitlepage,
    narroweqnarray,
    inline,
    oneside,
    ]{article}

\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{multirow}
\usepackage{float}
\floatstyle{boxed} 
\usepackage{subfig}
\usepackage{epsfig}
\usepackage{epstopdf}
\usepackage{epstopdf}

\begin{document}

\title{Trabajo Práctico 4: Algoritmos Genéticos \\
		(Corrección)}

\author{
	Luciano Mangiarotti (I.T.B.A),
	\and Federico Santos (I.T.B.A),
	\and Jimena Pose (I.T.B.A) \\ }

\maketitle

\section{Introducci\'on}

\noindent A continuación se presentan las explicaciones correspondientes a la elección de la temperatura de Boltzmann y la selección por Ruleta. Además se incluyen cuatro pruebas adicionales al informe entregado, para mostrar que el algoritmo genético funciona correctamente. \\

\noindent Por último se comparan los resultados obtenidos usando algoritmos genéticos con los resultados obtenidos al usar algoritmos de entrenamiento por \textit{back-propagation} para redes neuronales. \\

\noindent Los parámetros que se usan en las pruebas presentadas en este informe son los siguientes:

\begin{table}[h]
	\centering
    	\begin{tabular}{r l}
    		\hline \\
		Individuos en la población & 30 \\
		Brecha generacional $G$ & 0.7 \\
		Temperatura (Boltzmann) & 1000 \\
		Individuos seleccionados por \textit{Elite} & 3 \\
		Probabilidad de mutación & 0.001 \\
		Probabilidad de cruce & 0.95 \\
		Probabilidad de \textit{back-propagation} & 0.1 \\
		Pasos de \textit{back-propagation} & 100 \\
		Máxima cantidad de generaciones & 300 \\ \\
		\hline
	\end{tabular}
	\caption{Parámetros que permanecen fijos.}
	\label{tab:parametrosfijos}
\end{table}

\noindent Cabe destacar que a diferencia de los valores utilizados en el informe anterior, en este caso se reduce en un orden de magnitud la probabilidad de mutación y se aumenta la temperatura inicial para el método de Boltzmann. \\

\noindent En el Trabajo Número 4 se utilizó una probabilidad de mutación de $0.01$, la cual es elevada teniendo en cuenta la codificación de los individuos y el tamaño de la red neuronal utilizada. Por esta razón, se decidió optar por una probabilidad menor.\\

\noindent En el trabajo anterior, se utilizaba una cantidad de individuos seleccionados por Elite en métodos mixtos igual a 10. Se comprendió que la misma era una cantidad excesiva y se la redujo a 3, valor con el cuál se obtuvieron resultados satisfactorios.

\section{Temperatura Inicial en Boltzmann}

\noindent La temperatura inicial que se usó en las pruebas que se presentan en esta sección es $T_{inicial}=1000$. La misma decrece a lo largo de las generaciones según la ecuación:
\begin{equation}
	T = \frac{T_{inicial}}{N^{o} \hspace{0.1 cm} de \hspace{0.1 cm} Generacion+1}
\end{equation}

\noindent Resulta interesante evaluar la forma en que se modifica la probabilidad de seleccionar los distintos individuos a lo largo de las distintas generaciones. \\

\noindent En el Cuadro 2 se muestra la probabilidad de elegir a cada individuo de la población y su respectivo \textit{fitness} en la primera generación de una corrida determinada. \\

\begin{table}[h]
	\centering
    	\begin{tabular}{| c | c || c | c || c | c |}
    		\hline
		Fitness & Probabilidad & Fitness & Probabilidad & Fitness & Probabilidad \\
		\hline
		-6.06893 & 0.03341 & -8.09317 & 0.03334 & -9.03904   & 0.03331 \\
		-6.35175 & 0.03340 & -8.09462 & 0.03334 & -9.40982   & 0.03330 \\
		-7.21658 & 0.03337 & -8.10914 & 0.03334 & -9.46273   & 0.03330 \\
		-7.25205 & 0.03337 & -8.22834 & 0.03334 & -9.49188   & 0.03330 \\
		-7.26400 & 0.03337 & -8.34923 & 0.03333 & -9.75940   & 0.03329 \\
		-7.65424 & 0.03336 & -8.43193 & 0.03333 & -9.78279   & 0.03329 \\
		-7.79530 & 0.03335 & -8.51920 & 0.03333 & -9.93164   & 0.03328 \\
		-7.86203 & 0.03335 & -8.73062 & 0.03332 & -10.45224 & 0.03326 \\
		-7.87748 & 0.03335 & -8.90010 & 0.03332 & -10.53186 & 0.03326 \\
		-8.06176 & 0.03334 & -8.97096 & 0.03331 & -10.61998 & 0.03326 \\
		\hline
	\end{tabular}
	\caption{\textit{Fitness} de los distintos individuos y la probabilidad de elegirlos en la primera generación.}
	\label{tab:parametrosfijos}
\end{table}

\noindent Se observa que existe diversidad, es decir que los individuos tienen valores de \textit{fitness} bastante variados. No obstante, las probabilidades de elegir uno u otro son casi las mismas. \\

\noindent A medida que transcurren las generaciones la temperatura disminuye, haciendo que la probabilidad de elegir un individuo con mejor \textit{fitness} aumente. \\

\noindent En el Cuadro 3 se muestran las probabilidades luego de 2500 generaciones de la misma corrida. Luego de 2500 generaciones la probabilidad de elegir los individuos menos aptos es bastante menor que la de elegir uno bueno. \\

\begin{table}[h]
	\centering
    	\begin{tabular}{| c | c || c | c || c | c |}
    		\hline
		Fitness & Probabilidad & Fitness & Probabilidad & Fitness & Probabilidad \\
		\hline
		-0.66786 & 0.03437 & -0.66786 & 0.03437 & -0.66786 & 0.03437 \\
		-0.66786 & 0.03437 & -0.66786 & 0.03437 & -0.66786 & 0.03437 \\
		-0.66786 & 0.03437 & -0.66786 & 0.03437 & -0.66786 & 0.03437 \\
		-0.66786 & 0.03437 & -0.66786 & 0.03437 & -0.66795 & 0.03437 \\
		-0.66786 & 0.03437 & -0.66786 & 0.03437 & -0.66795 & 0.03437 \\
		-0.66786 & 0.03437 & -0.66786 & 0.03437 & -0.66795 & 0.03437 \\
		-0.66786 & 0.03437 & -0.66786 & 0.03437 & -0.67539 & 0.03373 \\
		-0.66786 & 0.03437 & -0.66786 & 0.03437 & -0.71698 & 0.03040 \\
		-0.66786 & 0.03437 & -0.66786 & 0.03437 & -0.77029 & 0.02660 \\
		-0.66786 & 0.03437 & -0.66786 & 0.03437 & -0.98911 & 0.01539 \\
		\hline
	\end{tabular}
	\caption{\textit{Fitness} de los distintos individuos y la probabilidad de elegirlos luego de 2500 generaciones.}
	\label{tab:parametrosfijos}
\end{table}

\noindent Hay que tener en cuenta que en este caso la diversidad es menor y que los individuos con igual \textit{fitness} tienen la misma probabilidad de ser elegidos.

\section{Selección por Ruleta:}

\noindent En el Trabajo 4, la implementación de ruleta le daba mayor probabilidad de ser elegido a los individuos con peor \textit{fitness}, lo cual es incorrecto. Lo correcto es que se le de mayor probabilidad a los individuos con mejor \textit{fitness}. Este inconveniente surgió debido a la función de aptitud utilizada.\\

\noindent Como todos los \textit{fitness} de los individuos son negativos, la división de un \textit{fitness} en particular por la suma de los \textit{fitness} de la población hace que se elimine el signo negativo. Por ese motivo se le daba más probabilidad al menor \textit{fitness}, es decir al \textit{fitness} más negativo. \\

\noindent Para solucionar este problema, se decidió sumarle a todos los fitness un valor positivo, de tal manera de llevar los valores de \textit{fitness} al campo de los positivos, donde el algoritmo de ruleta visto funciona correctamente, manteniendo las probabilidades de cada uno.

\section{Resultados y Conclusiones:}

\noindent En primer lugar, se analiza el comportamiento del método de selección basado en Boltzmann. Luego, se analizan los resultados al usar selección por ruleta. Se eligieron estos dos métodos, por ser los más representativos en esta situación. \\

\noindent En la Figura \ref{fig:grafico1} y la Figura \ref{fig:grafico2} se presentan los resultados obtenidos usando \textit{Elite-Boltzmann} como método de selección y reemplazo. En la primera se usa sólo el algoritmo genético y en la segunda se agrega el refinamiento de \textit{back-propagation}. \\

\noindent En ambas figuras se presenta en escala logarítmica la evolución del mejor \textit{fitness} de la población, el promedio del \textit{fitness} entre todos los individuos y el desvío estándar. Este último permite analizar la diversidad que hay en la población. \\

\noindent En la Figura \ref{fig:grafico1} se observa claramente cómo, sin hacer uso del refinamiento \textit{back-propagation}, el fitness del mejor individuo aumenta a lo largo de las generaciones. Esto muestra que el algoritmo genético funciona correctamente para el caso estudiado. Por otro lado, se puede observar que la velocidad con la que aumenta el mejor \textit{fitness} disminuye a lo largo de las generaciones. \\

\noindent El gráfico del desvío estándar permite observar que existe diversidad en la población a lo largo de la ejecución de las generaciones mostradas.\\

\noindent En la Figura \ref{fig:grafico2} se observa que haciendo uso del refinamiento \textit{back-propagation} se obtiene un mejor \textit{fitness} que cuando se usan solamente algoritmos genéticos, y en menos generaciones. En particular, el mejor \textit{fitness} obtenido es aproximadamente $-0.0409$, lo que corresponde a un error cuadrático medio de $0.0409$.\\

\noindent En las Figuras \ref{fig:grafico3} y \ref{fig:grafico4} se muestran los resultados obtenidos al utilizar el método \textit{Elite+Ruleta} para la selección y el reemplazo. En el Figura \ref{fig:grafico3} se muestran los resultados usando el algoritmo genético solo, y en el Figura \ref{fig:grafico4} se agrega la mejora de \textit{back-propagation}. \\

\noindent Al igual que en el ejemplo anterior, se muestra la evolución del máximo \textit{fitness} en escala logarítmica, el promedio del \textit{fitness} y su desvío estándar para poder analizar la diversidad de la población. \\

\noindent En la Figura \ref{fig:grafico3} se observa que, utilizando \textit{Elite+Ruleta}, también se logran resultados satisfactorios sin utilizar el refinamiento de \textit{back-propagation}. Como en el ejemplo anterior, se puede observar que la velocidad con la que aumenta el mejor \textit{fitness} disminuye a lo largo de las generaciones.\\

\noindent En la Figura \ref{fig:grafico4} se observa que en este caso, la incorporación del refinamiento de \textit{back-propagation} mejora considerablemente el mejor \textit{fitness} y hace que se requieran menos generaciones para alcanzarlo. En particular, luego de aproximadamente 100 generaciones, el aumento en el mejor \textit{fitness} es poco. El mejor \textit{fitness} obtenido es aproximadamente $-0.0681$, lo que corresponde a un error cuadrático medio de $0.0681$.\\

\noindent Según los resultados obtenidos, a partir de los cuatro gráficos mostrados, se puede concluir que con el refinamiento de \textit{back-propagation} se logra un mejor \textit{fitness} que sin utilizarlo. Sin embargo, aún sin éste, se logra que el algoritmo genético funcione de manera satisfactoria, aumentando el mejor \textit{fitness} de la población con el correr de la generaciones.

\subsection{Comparación con los algoritmos clásicos:}

\noindent Resulta interesante comparar los resultados obtenidos usando el código del trabajo práctico de Redes Neuronales, donde el entrenamiento se realizaba haciendo uso íntegramente del algoritmo \textit{back-propagation}. \\

\noindent Para poder hacer una comparación coherente entre los dos métodos de entrenamiento es necesario que los mismos se analicen en las mismas condiciones y con la mayor cantidad posible de parámetros iguales. \\

\noindent Para esto se entrena la red usando \textit{back-propagation} con los mismos patrones de las pruebas de algoritmos genéticos. Se contempla solamente el error de memorización y se usa \textit{momentum} ($\alpha = 0.1$).  \\

\noindent El la Figura \ref{fig:grafico5} se muestra el resultado de un entrenamiento con \textit{back-propagation} de la red neuronal haciendo uso del TP2, donde se puede ver cómo evoluciona el error cuadrático medio. Se usa escala logarítmica en el eje $y$.\\

\noindent Se observa cómo el error de memorización al que se llega luego de $1000$ épocas de entrenamiento es aproximadamente $0.1567$. Como se observa en las Figuras \ref{fig:grafico2} y \ref{fig:grafico4}, el error que se obtiene es mucho más pequeño, menos de la mitad.\\

\noindent En conclusión, el resultado que se obtuvo con los algoritmos genéticos haciendo uso de la mejora de \textit{back-propagation} proporcionó un error cuadrático medio más pequeño que utilizando solamente \textit{back-propagation}.

\clearpage

\begin{figure*}
        \centering
		\includegraphics[scale=0.6]{grafico1a.png}
        \caption[center]{Resultados usando \textit{Elite-Bolzman} para selección y reemplazo, sin
		la mejora de \textit{backpropagation}.}
       \label{fig:grafico1}
\end{figure*}

\begin{figure*}
        \centering
		\includegraphics[scale=0.6]{grafico2a.png}
        \caption[center]{Resultados usando \textit{Elite-Boltzmann} para selección y reemplazo, con
		la mejora de \textit{backpropagation}.}
       \label{fig:grafico2}
\end{figure*}

\begin{figure*}
        \centering
		\includegraphics[scale=0.6]{grafico3a.png}
        \caption[center]{Resultados usando \textit{Elite-Ruleta} para selección y reemplazo, sin la
		mejora de \textit{backpropagation}.}
       \label{fig:grafico3}
\end{figure*}

\begin{figure*}
        \centering
		\includegraphics[scale=0.6]{grafico4a.png}
        \caption[center]{Resultados usando \textit{Elite-Ruleta} para selección y reemplazo, con la
		mejora de \textit{backpropagation}.}
       \label{fig:grafico4}
\end{figure*}

\begin{figure*}
        \centering
		\includegraphics[scale=0.6]{grafico5a.png}
        \caption[center]{Evolución del error cuadrático medio en función de la cantidad de épocas
		usando el entrenamiento por \textit{back-propagation} clásico. }
       \label{fig:grafico5}
\end{figure*}


\end{document}